package 每日一题;

import java.util.Stack;

public class No844比较含退格的字符串 {

    /**
     * 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。
     * # 代表退格字符。
     * 注意：如果对空文本输入退格字符，文本继续为空。
     *
     * 示例 1：
     * 输入：S = "ab#c", T = "ad#c"
     * 输出：true
     * 解释：S 和 T 都会变成 “ac”。
     * 示例 2：
     * 输入：S = "ab##", T = "c#d#"
     * 输出：true
     * 解释：S 和 T 都会变成 “”。
     * 示例 3：
     * 输入：S = "a##c", T = "#a#c"
     * 输出：true
     * 解释：S 和 T 都会变成 “c”。
     * 示例 4：
     * 输入：S = "a#c", T = "b"
     * 输出：false
     * 解释：S 会变成 “c”，但 T 仍然是 “b”。
     *
     * 提示：
     * 1 <= S.length <= 200
     * 1 <= T.length <= 200
     * S 和 T 只含有小写字母以及字符 '#'。
     */

    public boolean backspaceCompare(String S, String T) {

        char[] c1 = S.toCharArray();
        char[] c2 = T.toCharArray();

        Stack<Character> stack1=new Stack<>();
        Stack<Character> stack2=new Stack<>();
        int oneIndex=0;
        int twoIndex=0;

        while (oneIndex<c1.length||twoIndex<c2.length){

            if(oneIndex<c1.length) {
                char one = c1[oneIndex++];
                if (one == '#') {
                    //出栈
                    if (!stack1.empty())
                        stack1.pop();
                } else {
                    //入栈
                    stack1.add(one);
                }
            }

            if(twoIndex<c2.length) {
                char two = c2[twoIndex++];
                if (two == '#') {
                    //出栈
                    if (!stack2.empty())
                        stack2.pop();
                } else {
                    //入栈
                    stack2.add(two);
                }
            }
        }

        return stack1.equals(stack2);
    }

}
